昨天的 coding practice 中，我們寫了用 linear search 取 pair 相加平均數為 passed argument 的解法，其實這樣做效率並不好，其Big O 為 O(n^2)

今天來介紹一個名為 Pointer 的概念

What is Pointer

• Pointer is not a formal name.Name is different everywhere, but the idea is the same.
• Using pointer helps reduce the complexity of algorithms
• Pointer can be used in many scenerio, such as boundarys /

所謂的Pointer就是箭頭 簡單說就是用一組箭頭去指向某些數字
從 Pointer 建立範圍 然後在該範圍進行運算並得出用於比較的結果

Pointer in the get average pair exercise

在 Find average pair 這個練習中，Pointer 用於界定兩元素的範圍
declare 要相加兩元素的 left & right

紅色箭頭即表示 current pointer
一步步將範圍縮小 直到範圍內沒有任何數字便結束function

提示：使用Pointer的概念

Answer:

const arrData = [-11, 0, 1, 2, 3, 9, 14, 17, 21];

function findAveragePair(arr, avgValue) {
    const result = [];
    let left = 0,right = arr.length - 1;
    while (left < right) {
        let tempAvg = arr[left] + arr[right] / 2;
        if (tempAvg > avgValue) {
            right--;
        } else if (tempAvg == avgValue) {
            result.push([arr[left], arr[right]]);
            left++;
            right--;
        } else {
            left++;
        }
    }
    return result;
}

averagePair(arrData,1.5); // 

改寫為 pointer 方法後，這次的 Big O 則成功降至 O(n)

Coding Practice Palindrome

Coding Practice Sebsequence Problem

相關資源

Algorithm Templates: Two Pointers
https://www.pluralsight.com/resources/blog/guides/algorithm-templates-two-pointers-part-1